package com.yuan.algorithms.动态规划;


/**
 * @author YouYuan
 * @contact 1265161633@qq.com
 * @date 2016年5月18日 上午9:23:55
 * @descript 给定两个序列X和Y，求X和Y长度最长的公共子序列。
 */
public class LCS {

	public static void main(String[] args) {
		String[] x = {"A", "B", "C", "B", "D", "A", "B"};
		String[] y = {"B", "D", "C", "A", "B", "A"};
		System.out.println();
		LCS(x, y);
	}

	private static void LCS(String[] x, String[] y) {
		int m = x.length;
		int n = y.length;
		int[][] b = new int[m+1][n+1];//标记匹配的路径
		int[][] c = new int[m+1][n+1];//记录匹配子序列元素的长度
		
		for (int i = 1; i <= m; i++) {
			for (int j = 1; j <= n; j++) {
				if (x[i-1].equals(y[j-1])) {//判断元素是否相等
					c[i][j] = c[i-1][j-1] + 1;//标记可以匹配当前元素，记录子序列长度+1
					b[i][j] = 1;//标记此处为子序列的元素
				} else if (c[i-1][j] >= c[i][j-1]) {//尝试匹配下一个元素
					c[i][j] = c[i-1][j];
					b[i][j] = 2;//标记元素的方向（i-1,j）
				} else {
					c[i][j] = c[i][j-1];
					b[i][j] = 3;//标记元素的方向（i,j-1）
				}
			}
		}
		printLCS(x, b, m, n);
	}

	/**
	 * 根据标记打印最长子序列
	 * @param x
	 * @param b 标记数组
	 * @param i 当前行位置
	 * @param j 当前列位置
	 */
	private static void printLCS(String[] x, int[][] b, int i, int j) {
		if (i==0 || j==0) {
			return;
		}
		if (b[i][j] == 1) {
			printLCS(x, b, i-1, j-1);
			System.out.print(x[i-1]);
		} else if (b[i][j] == 2) {
			printLCS(x, b, i-1, j);
		} else {
			printLCS(x, b, i, j-1);
		}
	}
}
